package com.javabasic.algorithm.leetcode;

/**
 * @Author xiongmin
 * @Description //TODO
 * @Date 2020/7/7 12:51
 * @Version 1.0
 **/
public class PathSum {

    public boolean hasPathSum(TreeNode root, int sum) {
        if (root == null) {
            return false;
        }
        int value = 0;
        return validate(root,value,sum);
    }

    /**
     * 遍历所有根到叶子节点的路径，判断是否有和sum相等的
     * @param root
     * @param value
     * @param sum
     * @return
     */
    private boolean validate(TreeNode root, int value, int sum) {
        if (root.right == null && root.left == null) {
            return value+root.val == sum;
        }
        if (root.right != null) {
            if (validate(root.right,value+root.val,sum)) {
                return true;
            }
        }
        if (root.left != null) {
            if (validate(root.left,value+root.val,sum)) {
                return true;
            }
        }
        return false;
    }
}
